﻿#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <string>
#include <stdbool.h>
#include <cstdio>


//根据二叉树创建字符串
//https://leetcode.cn/problems/construct-string-from-binary-tree/submissions/
//class Solution {
//public:
//    void Tree2str(TreeNode* root, string& s) {
//        if (!root) return;
//
//        s += to_string(root->val);
//
//        if (root->left || root->right)
//        {
//            s += '(';
//            Tree2str(root->left, s);
//            s += ')';
//        }
//        if (root->right)
//        {
//            s += '(';
//            Tree2str(root->right, s);
//            s += ')';
//        }
//
//
//    }
//    string tree2str(TreeNode* root) {
//        string s;
//        Tree2str(root, s);
//        return s;
//    }
//};

//二叉树的层序遍历
//https://leetcode.cn/problems/binary-tree-level-order-traversal/submissions/
//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//        vector<vector<int>> vv;
//
//        if (!root) return vv;
//
//        queue<TreeNode*> q;
//        q.push(root);
//        while (!q.empty())
//        {
//            int n = q.size();
//            vector<int> v;
//            while (n--)
//            {
//                TreeNode* node = q.front();
//                q.pop();
//                v.push_back(node->val);
//                if (node->left)
//                    q.push(node->left);
//                if (node->right)
//                    q.push(node->right);
//            }
//            vv.push_back(v);
//        }
//        return vv;
//    }
//};

//二叉树的最近公共祖先
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/submissions/
//低效率写法
//class Solution {
//public:
//
//    bool FindNode(TreeNode* root, TreeNode* x)
//    {
//        if (!root) return false;
//
//        return root == x
//            || FindNode(root->left, x)
//            || FindNode(root->right, x);
//    }
//
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        if (!root) return nullptr;
//        if (root == p || root == q) return root;
//
//        bool pleft = FindNode(root->left, p); //查找p是否在左子树
//        bool qleft = FindNode(root->left, q); //查找q是否在左子树
//
//        if ((pleft && !qleft) || (!pleft && qleft)) //分别在左子树和右子树
//            return root;
//        else if (pleft && qleft) //都在左子树
//            return lowestCommonAncestor(root->left, p, q); //去左子树中找
//        else
//            return lowestCommonAncestor(root->right, p, q); //去右子树中找
//
//    }
//};
//高效写法 - 转换链表寻找公共节点的问题
//class Solution {
//public:
//    bool TreePath(TreeNode* root, TreeNode* x, stack<TreeNode*>& s)
//    {
//        if (!root)
//            return false;
//
//        s.push(root);
//
//        if (root == x)
//            return true;
//
//        if (TreePath(root->left, x, s))
//            return true;
//
//        if (TreePath(root->right, x, s))
//            return true;
//
//        s.pop();
//        return false;
//    }
//
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        stack<TreeNode*> ps;
//        stack<TreeNode*> qs;
//        TreePath(root, p, ps);
//        TreePath(root, q, qs);
//        while (ps.top() != qs.top())
//        {
//            if (ps.size() > qs.size())
//            {
//                ps.pop();
//            }
//            else
//            {
//                qs.pop();
//            }
//        }
//        return ps.top();
//    }
//};


//二叉搜索树与双向链表
//https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
//class Solution {
//public:
//	void CreatMidOrd(TreeNode* root, TreeNode*& prev) //中序遍历创建
//	{
//		if (!root) return;
//
//		CreatMidOrd(root->left, prev);
//		root->left = prev;
//		if (prev)
//			prev->right = root;
//		prev = root;
//		CreatMidOrd(root->right, prev);
//	}
//
//	TreeNode* Convert(TreeNode* pRootOfTree) {
//		if (!pRootOfTree) return nullptr;
//
//		TreeNode* prev = nullptr;
//		CreatMidOrd(pRootOfTree, prev);
//		while (prev->left) { prev = prev->left; }
//		return prev;
//	}
//};

